package tree

import (
	"fmt"
	"math"
	"runtime"
	queue "structure/Queue"
)

type Node struct {
	data   interface{} //数据
	LChild *Node       //左
	RChild *Node       //右
}

type BinaryTree struct {
	Root   *Node
	deepin int //深度
}

//根据深度构建一个完全2插树

func recursionCreate(tree *Node, deepin int) {
	if deepin == 1 {
		return
	}
	lNode := new(Node)
	tree.LChild = lNode
	recursionCreate(lNode, deepin-1)
	RNode := new(Node)
	tree.RChild = RNode
	recursionCreate(RNode, deepin-1)

}

func CreateBinaryTree(deepin int) *BinaryTree {
	node := new(Node)
	node.data = nil
	node.LChild = nil
	node.RChild = nil

	recursionCreate(node, deepin) //创建树

	return &BinaryTree{
		deepin: deepin,
		Root:   node,
	}

}

func recursionByQueue(tree *Node, deepin int, linkQueue *queue.LinkQueue) {
	if deepin == 1 {
		return
	}

	data, _ := linkQueue.Pop()

	lNode := new(Node)
	lNode.data = data
	tree.LChild = lNode
	recursionByQueue(lNode, deepin-1, linkQueue)

	data, _ = linkQueue.Pop()

	RNode := new(Node)
	RNode.data = data
	tree.RChild = RNode
	recursionByQueue(RNode, deepin-1, linkQueue)

}

//根据队列生成
func CreateBinaryTreeByQueue(queue *queue.LinkQueue) *BinaryTree {
	num := queue.Length() + 1
	num = int(math.Logb(float64(num)))

	data, _ := queue.Pop()

	//构建Root节点
	node := new(Node)
	node.data = data
	node.LChild = nil
	node.RChild = nil

	recursionByQueue(node, num, queue)

	return &BinaryTree{
		deepin: num,
		Root:   node,
	}

}

const (
	Pre  = 0 //前序
	In   = 1 //中序
	Post = 2 //后序

)

func Order(node *Node, q *Query, mode int) {
	if node == nil {
		return
	}

	if mode == 0 {
		q.data = append(q.data, node.data)
	}

	Order(node.LChild, q, mode)
	if mode == 1 {
		q.data = append(q.data, node.data)
	}
	Order(node.RChild, q, mode)
	if mode == 2 {
		q.data = append(q.data, node.data)
	}

}

//mode模式
func (b *BinaryTree) OrderTraverse(mode int) *Query {
	q := NewQuery()

	Order(b.Root, q, mode)

	return q

}

func (b *BinaryTree) Depth() int {
	return b.deepin
}

//返回Root节点
func (b *BinaryTree) GetRoot() *Node {
	return b.Root
}

//判断空树
func (b *BinaryTree) Empty() bool {
	return b.Root.LChild == nil && b.Root.RChild == nil
}

//清空树
func (b *BinaryTree) Clear() {
	b.Root.data = nil
	b.Root.LChild = nil
	b.Root.RChild = nil
	runtime.GC()
}

func (b *BinaryTree) GetDeepin() int {
	if b.Empty() {
		return 1
	}

	node := b.Root

	i := 0
	for true {
		if node == nil {
			break
		}

		node = node.LChild
		i++

	}

	return i
}

func SearchTree(node *Node, mode int, cursor int, data *interface{}, end *int) {

	if cursor == *end || node == nil { //结束
		return
	}

	//前
	if mode == Pre && cursor != *end {
		*data = node.data
		*end++
	}
	SearchTree(node.LChild, mode, cursor, data, end)
	if mode == In && cursor != *end {
		*data = node.data
		*end++
	}

	SearchTree(node.RChild, mode, cursor, data, end)
	if mode == Post && cursor != *end {
		*data = node.data
		*end++
	}

}

func (b *BinaryTree) Value(cursor int, mode int) (interface{}, error) {

	if cursor > int(math.Pow(2.0, float64(b.Depth())))-1 {
		return nil, SearchValueErr
	}

	data := new(interface{})
	l := -1
	SearchTree(b.Root, mode, cursor, data, &l)
	fmt.Println(*data)
	return *data, nil

}

type BiThrNode struct {
	Node
	LTag bool
	RTag bool
}
